#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=3e3+10;
LL n,m,a[MAXN],sum[MAXN],f[MAXN],g[MAXN],q[MAXN];
double slope(LL x,LL y)
{
    return (g[x]-g[y]+sum[x]*sum[x]-sum[y]*sum[y])*1.0/(sum[x]-sum[y]);
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(LL i=1;i<=n;++i)scanf("%lld",&a[i]);
    for(LL i=1;i<=n;++i)
    {
        sum[i]=sum[i-1]+a[i];
        f[i]=sum[i]*sum[i];
    }
    memcpy(g,f,sizeof(f));
    for(LL j=2;j<=m;++j)
    {
        LL l=0,r=0;
        for(LL i=1;i<=n;++i)
        {
            while(l<r&&slope(q[l],q[l+1])<=2*sum[i])++l;
            LL t=q[l];
            f[i]=g[t]+(sum[i]-sum[t])*(sum[i]-sum[t]);
            while(l<r&&slope(q[r],i)<slope(q[r-1],q[r]))--r;
            q[++r]=i;
        }
        memcpy(g,f,sizeof(f));
    }
    printf("%lld\n",f[n]*m-sum[n]*sum[n]);
    return 0;
}
?
